package vj.dfs;


import vj.graph.Graph;
import vj.graph.Graph.AdjList;

public class DFSUtils {

	/*
	 * This method when run on a undirected disconnected graph produces DFS Forest.
	 */
	public static void DFS(Graph G, int s) {
		boolean visited[] = new boolean[G.V() + 1];
		/* vertex 1 is always the source, we are ignoring s*/
		for(int i = 1; i<= G.V(); i++) {
			if(visited[i] == false)
				DFSVisit(G, i, visited);
		}
	}
	
	private static void DFSVisit(Graph g, int v, boolean[] visited) {
		visited[v] = true;
		System.out.println("Visiting vertex:"+v);
		AdjList iterator = g.getAdjList(v);
		int w;
		if(iterator.hasNext()) {
			w = iterator.next();
			if(visited[w] == false)
				DFSVisit(g, w, visited);
			
		}
	}
	
	
	public static void Articulation(Graph G) {
		int vn[] = new int [G.V() + 1];
		int low[] = new int[G.V() + 1]; // can also called back[]. How much back in the tree can we go from a given vertex
		int time = 0;
		/*for(int i = 1; i <= G.V(); i++) {
			if(vn[i] == 0)
				arti(G, i, vn, low, time);
		}*/
		// First visiting vertex 2 from 1
		arti(G, 2, 1, vn, low, time);
	}
	/*
	 * This method will print all the articulation points in the Graph
	 * Visit v from u
	 */
	private static void arti(Graph g, int v, int u, int[] vn, int[] low, int time) {
		low[v] = vn[v] = time = time + 1;
		AdjList iterator = g.getAdjList(v);
		int w;
		if(iterator.hasNext()) {
			w = iterator.next();
			if(vn[w] == 0) {
				arti(g, w, v, vn, low, time);
				// updating while backtracking
				low[v] = Math.min(low[v], low[w]);
				if(vn[v] == 1 && vn[w] != 2) // Implies that root has more than one child in the DFS tree
					System.out.println("Vertex " + v + " is an articulation point.");
				if(vn[v] != 1 && low[w] >= vn[v]) // If v is a non-root vertex
					System.out.println("Vertex " + v + " is an articulation point.");
			} else {
				low[v] = Math.min(low[v], vn[w]);
			}
		}
	}
	
	public static void bridgeDetect(Graph g) {
		int color[] = new int[g.V() + 1];
		int d[] = new int[g.V() + 1];
		// reachable ancestor is also called low[] in skeina book
		int reachableAncestor[] = new  int[g.V() + 1];
		int time = 0;
		// Here 0 means parent of root. equivalent to passing null
		bridge(g, 1, 0, color, d, reachableAncestor, time);
	}
	
	/*
	 * Here the idea is to update low, the lowest number possible to reach.
	 * It's like we are trying to find back edge to u from v(tree rooted at v)
	 * 
	 * A non-root vertex u is an articulation vertex iff there exists a child v
		of u in the DFS tree such that low[v] >= dfsnum[u]. The root of the DFS tree is an articulation
		vertex iff it has more than one child.
	 */
	private static void bridge(Graph g,int u, int p, int[] color, int[] d, int[] reachableAncestor, int time) {
		color[u] = 1;
		reachableAncestor[u] = d[u] = time = time + 1;
		AdjList iterator = g.getAdjList(u);
		int v;
		while(iterator.hasNext()) {
			v = iterator.next();
			if(v != p) { // extra condition for not printing the immediate parent as a back edge
				if(color[v] == 0) { //(u, v) is a forward edge
					bridge(g, v, u, color, d, reachableAncestor, time);
					reachableAncestor[u] = Math.min(reachableAncestor[v], reachableAncestor[u]);
					if(reachableAncestor[v] > d[u])
						System.out.println("Edge "+ u +" -> " + v + " is a bridge");
				} else {
					// (u, v) is a back edge
					reachableAncestor[u] = Math.min(reachableAncestor[u], d[v]);
					//System.out.println("Edge "+ u +" -> " + v + " is a back edge");
				}
			}
		}
		
	}
	
	public static void DFS1(Graph G, int s) {
		boolean discovered[] = new boolean[G.V() + 1];
		boolean processed[] = new boolean[G.V() + 1];
		int parent[] = new int[G.V() + 1];
		int entry_time[] = new int[G.V() + 1];
		int exit_time[] = new int[G.V() + 1];
		int time = 0;
		//DFSVisit1(G, s, discovered, processed, parent, entry_time, exit_time, time);
		DFSVisitCycleDetect(G, s, discovered, processed, parent, entry_time, exit_time, time);
		
	}
	
	private static void DFSVisit(Graph G, int v, boolean[] disc, boolean[] proc, int parent[], int[] ent_time, int[] ext_time, int time) {
		int y;
		disc[v] = true;
		time = time + 1;
		ent_time[v] = time;
		AdjList iterator = G.getAdjList(v);
		while(iterator.hasNext()) {
			y = iterator.next();
			if(disc[y] == false) {
				parent[y] = v;
				process_edge(v,y, parent);
				DFSVisit(G, y, disc, proc, parent, ext_time, ent_time, time);
			} else if(!proc[y]) {
				process_edge(v,y, parent);
			}
		}
		time = time + 1;
		ext_time[v] = time;
		proc[v] = true;
	}
	
	/* In this method each edge is processed only once */
	private static void DFSVisitCycleDetect(Graph G, int v, boolean[] disc, boolean[] proc, int parent[], int[] ent_time, int[] ext_time, int time) {
		int y;
		disc[v] = true;
		time = time + 1;
		ent_time[v] = time;
		AdjList iterator = G.getAdjList(v);
		while(iterator.hasNext()) {
			y = iterator.next();
			if(disc[y] == false) {
				parent[y] = v;
				process_edge(v,y, parent);
				DFSVisitCycleDetect(G, y, disc, proc, parent, ext_time, ent_time, time);
			} else if(!proc[y]) {
				process_edge(v,y, parent);
			}
		}
		time = time + 1;
		ext_time[v] = time;
		proc[v] = true;
	}
	
	
	private static void process_edge(int v, int y, int parent[]) {
		System.out.println("Processing edge " + v + " -> " + y + " ");
	}
	
	private static void process_edge_cycle(int v, int y, int parent[]) {
		if(parent[v] != y) {
			System.out.println("Found a cycle from "+y+" to "+ v);
		}
		System.out.println("Processing edge " + v + " -> " + y + " ");
	}
}
